/*
 * @lc app=leetcode.cn id=494 lang=cpp
 *
 * [494] 目标和
 *
 * https://leetcode.cn/problems/target-sum/description/
 *
 * algorithms
 * Medium (49.03%)
 * Likes:    1202
 * Dislikes: 0
 * Total Accepted:    222.9K
 * Total Submissions: 454.6K
 * Testcase Example:  '[1,1,1,1,1]\n3'
 *
 * 给你一个整数数组 nums 和一个整数 target 。
 * 
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * 
 * 
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 
 * 
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1], target = 1
 * 输出：1
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * 0 
 * 0 
 * -1000 
 * 
 * 
 */

// @lc code=start
class Solution {

// // 回溯法-组合总和，但是前提是考虑清楚为什么是组合总和，left为什么求出来的
// private:
//     vector<int> path;
//     int res;
//     void backtracking(vector<int>& nums, int target, const int &sum, int startIndex) {
//         if(sum > target) return;
//         if(target == sum) {
//             res++;
//         }

//         for(int i = startIndex; i < nums.size() && sum + nums[i] <= target; i++) {
//             // if(sum + nums[i] > target) break;
//             path.push_back(nums[i]);
//             backtracking(nums, target, sum + nums[i], i + 1);
//             path.pop_back(); 
//         }
//     }
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         int sum = 0; 
//         for(int i = 0; i < nums.size(); i++) {
//             sum += nums[i];
//         }
//         if(sum < abs(target)) return 0;
//         if((sum + target) % 2) return 0;

//         int left = (sum + target) / 2;

//         path.clear();
//         res = 0;
//         sort(nums.begin(), nums.end()); // 需要排序
//         backtracking(nums, left, 0, 0);
//         return res;

//      }


// 动态规划
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        /*
            有正有负，分为两拨，left（正） 和 right（负） 目的：左边右边结合计算结果是target
            left + right = sum -->是固定的
            target 也是固定的
            target = left -right = left - (sum - left)=2 * left - sum
            由此计算可得：left = (target + sum) / 2
            因此，要求的结果是容量是left的背包，有几种组合相加结果是left
        */
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];
        if(sum < abs(target)) return 0;
        if((target + sum) % 2) return 0;

        int bagSize = (target + sum) / 2;
        
        // dp[j] 表示 容量是j的背包，装 满 物品时，有dp[j]种方法
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;

        for (int i = 0; i < nums.size(); i++) {
            cout<<"第 "<<i<<" 个背包: ";
            for (int j = bagSize; j >= nums[i]; j--) {
                // 还原 dp[j] = dp[j] + dp[j-nums[i]]
                // 现在是某一行，nums[i]的外循环，在内循环中，背包重量从大到小遍历
                // 其中dp[j]表示的是上一行nums[i-1]的方法数，
                // 那后边的dp[j-nums[i]]当前背包重量j减去即将添加的nums[i]的重量，剩余重量装满最大的方法数，
                // 其实也就是nums[i-1]这一行的，只不过是粘贴了这一行，直接进行计算的，也就是为什么j从右向左遍历
                // 最终实现的结果就是所有行的从上到下的累加
                dp[j] += dp[j - nums[i]];
                cout<<"dp["<<j<<"] = "<<dp[j]<<" ";
            }
            cout<<endl;
        }
        return dp[bagSize];
    }

};
// @lc code=end

